|
This article describes the drift-plus-penalty method for optimization of queueing networks and other stochastic systems. ==Introduction to the drift-plus-penalty method== The drift-plus-penalty method refers to a technique for stabilizing a queueing network while also minimizing the time average of a network penalty function. It can be used to optimize performance objectives such as time average power, throughput, and throughput utility. 〔 M. J. Neely, "Energy Optimal Control for Time Varying Wireless Networks," IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006. 〕 〔 M. J. Neely, E. Modiano, and C. Li, "Fairness and Optimal Stochastic Control for Heterogeneous Networks," Proc. IEEE INFOCOM, March 2005. 〕 In the special case when there is no penalty to be minimized, and when the goal is to design a stable routing policy in a multi-hop network, the method reduces to backpressure routing. 〔L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks, ''IEEE Transactions on Automatic Control'', vol. 37, no. 12, pp. 1936-1948, Dec. 1992. 〕 〔 L. Georgiadis, M. J. Neely, and L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks," ''Foundations and Trends in Networking'', vol. 1, no. 1, pp. 1-149, 2006. 〕 The drift-plus-penalty method can also be used to minimize the time average of a stochastic process subject to time average constraints on a collection of other stochastic processes. 〔 M. J. Neely. ''Stochastic Network Optimization with Application to Communication and Queueing Systems,'' Morgan & Claypool, 2010. 〕 This is done by defining an appropriate set of virtual queues. It can also be used to produce time averaged solutions to convex optimization problems. 〔 M. J. Neely, "Distributed and Secure Computation of Convex Programs over a Network of Connected Processors," DCDIS Conf, Guelph, Ontario, July 2005 〕 〔 S. Supittayapornpong and M. J. Neely, "Quality of Information Maximization for Wireless Networks via a Fully Separable Quadratic Policy," arXiv:1211.6162v2, Nov. 2012. 〕 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Drift plus penalty」の詳細全文を読む スポンサード リンク
|